
// 使用前序求的就是深度，使用后序求的是高度。
// 二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数。
// 二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数。

#include "definition.h"
class Solution {
 public:
  // 前序遍历，求深度(即自顶向下的递归)
  int result = 0;
  void getdepth(TreeNode* node, int depth) {
    result = depth > result ? depth : result;
    if (!node->left && !node->right) return;
    if (node->left) {
      getdepth(node->left, depth + 1);  // 回溯
    }
    if (node->right) {
      getdepth(node->right, depth + 1);  // 回溯
    }
    return;
  }
  int maxDepth(TreeNode* root) {
    if (!root) return 0;
    getdepth(root, 1);
    return result;
  }
  // 本题求的是最大深度，即最大高度，所以也可使用后序遍历
  // 后序遍历，求高度(即自底向上的递归)
  int maxDepth(TreeNode* root) {
    if (!root) return 0;
    int left = 1 + maxDepth(root->left);
    int right = 1 + maxDepth(root->right);
    return max(left, right);
  }
};